﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 分割链表

// 定义结构体
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}LN;

// 创建节点
LN* buynode(int x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

LN* partition(LN* head, int x)
{
	// 如果是空链表，直接返回
	if (head == NULL)
	{
		return head;
	}
	// 创建两个带头链表
	LN* pucr, * puend;
	pucr = puend = buynode(-1);

	LN* ptile, * ptend;
	ptile = ptend = buynode(-1);

	LN* per = head;
	//遍历，将小于形参的数放pucr 
	// 将大于形参的数放ptile 
	while (per)
	{
		if (per->val < x)
		{
			puend->next = per;
			puend = puend->next;
		}
		else
		{
			ptend->next = per;
			ptend = ptend->next;
		}
		per = per->next;
	}
	// 合并大小链表
	ptend->next = NULL;
	puend->next = ptile->next;
	LN* ret = pucr->next;
	free(pucr);
	free(ptile);
	return ret;
}

// 创建链表
LN* SList()
{
	LN* head = buynode(-1);
	LN* p = head;
	int arr[] = { 1,4,3,2,5,2 };
	for (int i = 0; i < 6; i++)
	{
		p->next = buynode(arr[i]);
		p = p->next;
	}
	LN* ret = head->next;
	free(head);
	return ret;
}

// 打印链表
void PrintList(LN* head)
{
	while (head)
	{
		printf("%d ", head->val);
		head = head->next;
	}
	printf("\n");
}
int main()
{
	LN* head = SList();
	PrintList(head);
	LN* ret = partition(head, 3);
	PrintList(ret);
	return 0;
}